// Package _2__矩阵中的路径 main
// @Title _2__矩阵中的路径
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-12 14:23
// @Create  2022-01-12 14:23
package main

import "fmt"

func main() {
	word := "ABCCED"
	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	fmt.Println(exist(board, word))
}

// 遍历每一个元素，查询是否能以当前元素开头找到对应的路径
func exist(board [][]byte, word string) bool {
	if len(board) == 0 {
		return false
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if findRoad(board, i, j, 0, word) {
				return true
			}
		}
	}
	return false
}

/**
 * @Description:
 * @param board 二维矩阵
 * @param x 当前搜索元素的x坐标
 * @param y 当前搜索元素的y坐标
 * @param target 当前美枚举到的目标单词word的下标
 * @param word  要搜索的字符串
 * @return bool 是否能搜到
 */
func findRoad(board [][]byte, x, y, target int, word string) bool {
	if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) || board[x][y] != word[target] {
		return false
	}
	// 索引等于单词长度-1，说明全匹配上了
	if target == len(word)-1 {
		return true
	}
	temp := board[x][y]
	board[x][y] = '.' // 立马感染
	// 四个方向遍历
	res := findRoad(board, x-1, y, target+1, word) ||
		findRoad(board, x+1, y, target+1, word) ||
		findRoad(board, x, y-1, target+1, word) ||
		findRoad(board, x, y+1, target+1, word)
	// 如果搜不到 记得撤回感染
	board[x][y] = temp
	return res
}
